from solver import Solver
from verifier import Verifier
import copy
import random


class GreedySolver(Solver):
    def __init__(self, data_path='data.txt'):
        super().__init__(data_path=data_path)
        self.verifier = Verifier(data_path=data_path)

    def solve(self):
        sol = self.tabu_search_base_GA()
        return sol

    def _put_step_into_machine(self, time_table, component_idx, component_step_idx, time_period, now_time, is_insert=True):
        if len(time_table) == 0:
            if is_insert:
                time_table.append((component_idx, component_step_idx, now_time, now_time + time_period))
            return now_time + time_period
        for i in range(len(time_table)):
            if now_time + time_period <= time_table[i][2]:
                if is_insert:
                    time_table.insert(i, (component_idx, component_step_idx, now_time, now_time + time_period))
                return now_time + time_period
            now_time = max(now_time, time_table[i][3])
        if is_insert:
            time_table.insert(len(time_table), (component_idx, component_step_idx, now_time, now_time + time_period))
        return now_time + time_period

    # 禁忌搜索
    def tabu_search(self):
        width = 1
        length = 1000
        init_num = 10
        q = self._tabu_search_init(init_num=init_num)
        pos = 0
        best_sol = None
        best_val = 1000000000
        while pos < len(q) < length:
            sol, val = self._tabu_search_pso_to_sol(q[pos])
            if val < best_val:
                best_val = val
                best_sol = sol
            tmp_width = 0
            for i in range(1, len(q[pos])):
                new_pso = copy.deepcopy(q[pos])
                idx = i
                while idx < len(new_pso) and new_pso[idx] != new_pso[idx - 1]:
                    new_pso[idx - 1], new_pso[idx] = new_pso[idx], new_pso[idx - 1]
                    sol2, val2 = self._tabu_search_pso_to_sol(new_pso)
                    if val2 < val:
                        tmp_width += 1
                        q.append(new_pso)
                        if val2 < best_val:
                            best_val = val2
                            best_sol = sol2
                        break
                    idx += 1
                if tmp_width >= width:
                    break
                new_pso = copy.deepcopy(q[pos])
                idx = i - 1
                while idx >= 1 and new_pso[idx] != new_pso[idx - 1]:
                    new_pso[idx - 1], new_pso[idx] = new_pso[idx], new_pso[idx - 1]
                    sol2, val2 = self._tabu_search_pso_to_sol(new_pso)
                    if val2 < val:
                        tmp_width += 1
                        q.append(new_pso)
                        if val2 < best_val:
                            best_val = val2
                            best_sol = sol2
                        break
                    idx -= 1
                if tmp_width >= width:
                    break
            pos += 1
        return best_sol

    # 基于遗传算法的禁忌搜索
    def tabu_search_base_GA(self):
        width = 1
        length = 1000
        init_num = 10
        # q = self._tabu_search_init(init_num=init_num)
        from hyj.GA import GA
        ga = GA(self.data)
        ans = ga.run()
        q = [ans[2]]
        pos = 0
        best_sol = None
        best_val = 1000000000
        while pos < len(q) < length:
            sol, val = self._tabu_search_pso_to_sol(q[pos])
            if val < best_val:
                best_val = val
                best_sol = sol
            tmp_width = 0
            for i in range(1, len(q[pos])):
                new_pso = copy.deepcopy(q[pos])
                idx = i
                while idx < len(new_pso) and new_pso[idx] != new_pso[idx - 1]:
                    new_pso[idx - 1], new_pso[idx] = new_pso[idx], new_pso[idx - 1]
                    sol2, val2 = self._tabu_search_pso_to_sol(new_pso)
                    if val2 < val:
                        tmp_width += 1
                        q.append(new_pso)
                        if val2 < best_val:
                            best_val = val2
                            best_sol = sol2
                        break
                    idx += 1
                if tmp_width >= width:
                    break
                new_pso = copy.deepcopy(q[pos])
                idx = i - 1
                while idx >= 1 and new_pso[idx] != new_pso[idx - 1]:
                    new_pso[idx - 1], new_pso[idx] = new_pso[idx], new_pso[idx - 1]
                    sol2, val2 = self._tabu_search_pso_to_sol(new_pso)
                    if val2 < val:
                        tmp_width += 1
                        q.append(new_pso)
                        if val2 < best_val:
                            best_val = val2
                            best_sol = sol2
                        break
                    idx -= 1
                if tmp_width >= width:
                    break
            pos += 1
        return best_sol

    def _tabu_search_init(self, init_num=1):
        n = self.data.n
        a = self.data.a
        seq = list()
        for i in range(n):
            for j in range(len(a[i])):
                seq.append(i)
        q = list()
        for _ in range(init_num):
            random.shuffle(seq)
            q.append([i for i in seq])
        return q

    def _tabu_search_pso_to_sol(self, pso):
        n = self.data.n
        m = self.data.m
        a = self.data.a
        sol = [list() for _ in range(m)]
        cp_time = [0] * n
        cp_step = [0] * n
        for ele in pso:
            i = ele
            j = cp_step[i]
            cp_time_tmp = [0] * len(a[i][j])
            for k in range(len(a[i][j])):
                machine_idx = a[i][j][k][0]
                time = a[i][j][k][1]
                cp_time_tmp[k] = self._put_step_into_machine(sol[machine_idx], i, j, time, cp_time[i], is_insert=False)
            k = cp_time_tmp.index(min(cp_time_tmp))
            machine_idx = a[i][j][k][0]
            time = a[i][j][k][1]
            cp_time[i] = self._put_step_into_machine(sol[machine_idx], i, j, time, cp_time[i])
            cp_step[i] += 1
        return sol, max(cp_time)

    # 按启发式估值排序 只考虑k=1的情况
    def greedy_by_heuristic_valuation(self):
        n = self.data.n
        m = self.data.m
        a = self.data.a
        cp_time = [0] * n
        cp_left_long = [0] * n
        for i in range(n):
            for j in range(len(a[i])):
                cp_left_long[i] += a[i][j][0][1]
        step = [0] * n
        sol = [list() for _ in range(m)]
        while True:
            pos = -1
            val = -1
            for i in range(n):
                if step[i] == len(a[i]):
                    continue
                machine_time = 0
                if len(sol[a[i][step[i]][0][0]]) > 0:
                    machine_time = sol[a[i][step[i]][0][0]][-1][-1]
                if cp_left_long[i] + max(cp_time[i], machine_time) > val:
                    val = cp_left_long[i] + max(cp_time[i], machine_time)
                    pos = i
            if pos == -1:
                break
            machine_idx = a[pos][step[pos]][0][0]
            time = a[pos][step[pos]][0][1]
            cp_time[pos] = self._put_step_into_machine(sol[machine_idx], pos, step[pos], time, cp_time[pos])
            cp_left_long[pos] -= time
            step[pos] += 1
        return sol

    # 搜索优先级的顺序贪心 只考虑k=1的情况
    def search_base_greedy_by_order(self):
        n = self.data.n
        m = self.data.m
        a = self.data.a
        best_sol = None
        best_val = 1000000000
        for num in range(n ** n):
            tmp = num
            rank = list()
            for i in range(n):
                rank.append(tmp % n)
                tmp //= n
            if len(list(set(rank))) != n:
                continue
            sol = [list() for _ in range(m)]
            for i in rank:
                now = 0
                for j in range(len(a[i])):
                    machine_idx = a[i][j][0][0]
                    time = a[i][j][0][1]
                    now = self._put_step_into_machine(sol[machine_idx], i, j, time, now)
            self.verifier.load_sol_from_param(sol=sol)
            # self.verifier.verify(show_info=False)
            if self.verifier.get_finished_time() < best_val:
                best_val = self.verifier.get_finished_time()
                best_sol = sol
        return best_sol

    # 简单顺序贪心 只考虑k=1的情况
    def simple_greedy_by_order(self):
        n = self.data.n
        m = self.data.m
        a = self.data.a
        sol = [list() for _ in range(m)]
        for i in range(n):
            now = 0
            for j in range(len(a[i])):
                machine_idx = a[i][j][0][0]
                time = a[i][j][0][1]
                now = self._put_step_into_machine(sol[machine_idx], i, j, time, now)
        return sol
